package xyz.scootaloo.oj.iq

import org.junit.Test
import xyz.scootaloo.oj.ds.ListNode
import xyz.scootaloo.oj.ds.helper.CollectionHelper

/**
 * @author flutterdash@qq.com
 * @since 2021/4/16 21:24
 */
class M0201 {

    private fun removeDuplicateNodes(head: ListNode?): ListNode? {
        if (head == null) return null
        val cache = IntArray(628)

        var pointer = head
        while (pointer?.next != null) {
            put(cache, pointer.`val`)
            if (contains(cache, pointer.next.`val`)) {
                pointer.next = pointer.next?.next
            } else {
                put(cache, pointer.`val`)
                pointer = pointer.next
            }
        }

        return head
    }

    private val base = 1

    // capacity 20096
    private fun put(cache: IntArray, number: Int) {
        val index = number.shr(5) // number / 32
        val offset = number % 32
        cache[index] = cache[index].or(base.shl(offset))
    }

    private fun contains(cache: IntArray, number: Int): Boolean {
        val index = number.shr(5) // number / 32
        val offset = number % 32
        return cache[index].and(base.shl(offset)) != 0
    }

    @Test
    fun testCache() {
        val cache = IntArray(628)
        put(cache, 1)
//        put(cache, 2)
//        put(cache, 3)
        put(cache, 31)
        put(cache, 32)
        put(cache, 33)
        println(contains(cache, 1))
        println(contains(cache,32))
        println(contains(cache,33))
        println(contains(cache,35))
    }

    @Test
    fun test0() {
        val node11 = ListNode(1)
        val node12 = ListNode(1)
        val node13 = ListNode(1)
        val node14 = ListNode(1)
        val node2 = ListNode(2)
        node11.next = node12
        node12.next = node13
        node13.next = node14
        node14.next = node2
        CollectionHelper.showListNodes(removeDuplicateNodes(node11))
    }

    @Test
    fun test1() {
        val node11 = ListNode(1)
        val node12 = ListNode(2)
        val node13 = ListNode(3)
        val node23 = ListNode(3)
        val node22 = ListNode(2)
        val node21 = ListNode(1)
        node11.next = node12
        node12.next = node13
        node13.next = node23
        node23.next = node22
        node22.next = node21
        CollectionHelper.showListNodes(removeDuplicateNodes(node11))
    }

}
